Link structure analysis of urban road networks for identifying traffic congestion

NetSci 2016 - Diffusion and Transport

Thursday, June 2, 2016 / 16:10-17:50 / Dongkang C, Avenue 3F

Wei Chien Benny Chin, Tzai Hung Wen, and Pei Chun Lai (National Taiwan University, Taiwan)

3 important concepts for identifying congestion distribution

  • the connectivity: how well is this street (in terms of bringing people to their destination)?
  • the demands: how many is the vehicles?
  • the design: is its network structure too complex (lots of turning)?

The aim of this study is to understand

the network characteristics that influence the occurance of

traffic congestion.

two components:

moving cars and interconnected streets

imagine,
the streets are connected to each other, and
there are lots of cars moving on
the streets...

  • This is similar to the hyperlinks network of webpages, where people surf from one webpage to another, by the "links".

this study begin with a simple model

When a car is moving on a street, it moves along the street.
When it comes to an intersection, it might keep moving straight, or take a turn to the left/right.

At first,
lets just assume that the turning probabilities to the different directions are equal.

simulating car movements with random turns random turn
turning probability to any next street segment = $ 1/3 $

In [2]:
canvas = toyplot.Canvas(450, 450)
axes = canvas.cartesian()
line = axes.plot(lx,ly, style={"stroke":"steelblue", "stroke-width":10})
line = axes.plot(ly,lx, style={"stroke":"steelblue", "stroke-width":5})
mark = axes.scatterplot(x, y, size=20, marker='s')
canvas.animate(len(x) + 1, callback)
01002003000100200300

expanded the simple model with the real street network (of Taipei City)

In [3]:
from IPython.display import HTML
HTML('<iframe src="https://player.vimeo.com/video/168713881" width="640"\
height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen \
allowfullscreen></iframe><p><a href="https://vimeo.com/168713881">\
simulation - moving cars on streets taking turn randomly - v0.2</a>\
from <a href="https://vimeo.com/user11082431">Benny Chin</a> on \
<a href="https://vimeo.com">Vimeo</a>.</p>')

this model is similar to the concept behind Google's PageRank (PR) algorithm.

PageRank uses a random move model (the random surfer),
and analyzes the hyperlink connectivity,
namely the referencing network,
to identify the key webpages.
"which pages are referenced more than others."

basic-form: PageRank (Brin & Page, 1998)
$ PR_{t}(i) = \sum_{j\in IN(i)} PR_{t-1}(j) \times \frac{1}{outdeg(j)} $
$ IN(i) $: the incoming node set of i; $ outdeg(j) $: the out-degree of j.

the concept of the PageRank (basic form) webpage network
the probability to select each option $ = 1/3 $

Therefore,
we can run the PageRank on the street network,
to identify the important street segment where there are lots of cars would pass by.

The output of PageRank, the score of each street, could be used to represent how important the street is.

the potential demand of the street

But,

the movements of cars are not completely random in the real world.

main street vs. secondary street
main street vs. secondary street

Most of the cars will move along the main direction (keep moving straight).

to capture this concept in the model,
we introduce the "attractiveness" ($attr$) of street segment.

$ attr =$ a composite variable that differentiate the streets by their ability to attract cars.

turning probability:
$ turning = \frac{attr(i)}{\sum_{k\in OUT(j)}attr(k)} $

but, how do we know the distribution of the attractiveness?

  • we use Genetic Algorithm (GA) to calibrate the atttractiveness of every street segment by using the VD flow data.
  • fitness of GA: the rank correlation between FBPR and the known VD flow.

the modified PR: Flow-based PageRank (FBPR):
$ FBPR_{t}(i) = \sum_{j\in IN(i)} FBPR_{t-1}(j) \times turning $

In [5]:
canvas = toyplot.Canvas(450, 450)
axes = canvas.cartesian()
line = axes.plot(lx,ly, style={"stroke":"steelblue", "stroke-width":10})
line = axes.plot(ly,lx, style={"stroke":"steelblue", "stroke-width":5})
mark = axes.scatterplot(x2, y2, size=20, marker='s')
canvas.animate(len(x2) + 1, callback)
01002003000100200300

While
the turning probability could be calculated from the calibrated attractiveness,

we could measure

the local complexity of a street.

$ entropy(j) = -\sum_{k \in OUT(j)} (turning(j,k) \times ln(turning(j,k))) $

the outgoing entropy

the entropy of the turning probabilities origin from the street.

hierarchy vs. uniform entropy
the outgoing entropy -- local complexity

in summary,

  • 2 components: moving cars and street network
  • turning probabilities are different between the outgoing street
  • the FBPR scores could be used to capture the potential demand
  • the outgoing entropy represent the local complexity of each street

the three concepts about the congestion

  • connectivity: run a modified PR algorithm (FBPR) on the street network
  • potential demand: the distribution of FBPR scores
  • local complexity: the distribution of outgoing entropy

Traffic Congestion

the everyday problem for most of the cities in the world.

In most developing countries, the capacity of streets do not meet the rising number of car owners, hence the congestion problem become more serious.

congestion: a spatial-temporal network problem. google traffic
Taipei City

(apart from unexpected factors, e.g. accidents)
Traffic congestion happens while
lots of people go to the same destinations (works, schools) at the same time, putting huge pressure on the street network.


on rush hours

  • demand increase
  • if the street is complex, the area would easily get into congestion

framework

in order to analyze the connectivity of streets, and to measure the demands and design of each street
we propose the Flow-based PageRank.

study framework
the study framework

something about Taipei
Taipei City

the connectivity

the ability of streets for bringing people to their destination.

  • analysis unit (nodes): street segment
  • connection (links): intersection of street segments
  • network: the dual graph of street network

dual representation
from street network to its dual graph

the (potential) demands

the potential number of vehicles passing by the street?

the vehicle detector (VD) data: the real traffic volume data

  • a sensor under the street, that count the number of vehicles that is passing above it.
  • located at most of the major streets in Taipei City

VD location and study area
the street network, and VD location

the design

is the network structure too complex?

  • moving speed will be slowed down if more vehicles are turning to different direction from a same street.
  • the complexity of turning probability between streets is a key measurement to understand traffic congestion </small>

results

the simulation

In [6]:
HTML('<iframe src="https://player.vimeo.com/video/168714357" width="640"\
height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen \
allowfullscreen></iframe><p><a href="https://vimeo.com/168714357">\
simulation - moving cars on streets turning with the estimated probability\
- v0.2</a> from <a href="https://vimeo.com/user11082431">Benny Chin</a>\
on <a href="https://vimeo.com">Vimeo</a>.</p>')

The distributions of FBPR and outgoing entropy

FBPR distribution
the FBPR distribution

outgoing entropy distribution
the outgoing-entropy distribution

The estimated location of congestion

congested segment
the congested segment: top FBPR overlaped with top entropy

discussions

from a simple model, to the congestion framework

  • 2 components: moving cars & interconnected streets
  • include the idea of attractiveness
  • calculate the turning probability
  • estimate the potential demands
  • measure the local complexity

to understand an everyday problem

Is the design of the street network meant to be easily get into congestion?

if lots of cars started moving at the same times,
will the city become congested easily?

the connectivity

  • are the streets are connected in an appropriate way?
  • are there enough alternative routes that cost similar?

Where are the cars concentrated?

  • how many cars will pass by a street?
  • assuming that cars will now disappear, the cars will always move from one street to a connected street.
  • the calculation of the converged FBPR scores will uncover the distribution of the potential needs of movements.

the potential demands

Where will the cars turn?

  • are the cars turn to the same direction?
  • outgoing entropy of the turningt probabilities of each street tells us the complexity of the street.
  • if the street is less complex, its hierarchy is more significant.eet.

the local complexity

Thats all, thanks.

my contact info: Benny Chin,
wcchin.88@gmail.com
a Ph.D. student at National Taiwan University.

links: